By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.
By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.
Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.
In [1]:
from sympy import sieve
from itertools import combinations, product
primes = set(sieve.primerange(10**5, 10**6))
powers = [10, 100, 1000, 10000, 100000]
smallest_prime = 999999
for i in [1,2,3,4]:
for j in range(i):
pattern = 111110 - powers[i] - powers[j]
for a in range(10):
for b in range(10):
for c in 1, 3, 7, 9:
current_prime = 0
strikes = 0
N = a*powers[i] + b*powers[j] + c
for k in range(10):
if N > smallest_prime:
break
if not (N in primes):
strikes += 1
if strikes > 2:
break
elif current_prime == 0:
current_prime = N
N += pattern
else:
print(current_prime)
smallest_prime = min(smallest_prime, current_prime)
Explanation: We search for examples with up to six digits. The number of asterisks must be a multiple of 3, since otherwise at least two of the numbers obtained by replacing the asterisks with a digit will be divisible by 3. For example, the pattern 56**3 generates the 10 numbers {56003, 56113, 56223, ..., 56993}, and three of these numbers are divisible by 3 (56223, 56553, and 56883). Clearly the last digit in the pattern cannot be an asterisk, since a prime greater than 5 can end only in 1, 3, 7, or 9.
In the code, pattern is a six-digit number with three 0s and three 1s, such as 110100. The ones indicate the positions of the asterisks, and the zeros indicate positions where other digits a, b, c can be placed. For example, if pattern = 110100, a = 5, b = 6, and c = 7, then the candidate primes are 005067, 115167, 225267, ..., 995967. We search for examples of this sort in which 8 out of the 10 candidates are prime.